/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package servidorbancos.geneticos;

import java.util.*;
import servidorbancos.resources.Agencia;
import servidorbancos.resources.Distancia;

/**
 *
 * @author thiago.araujo
 */
public class AlgoritmoGenetico {
    
    int nIteracoes = 10000, geracoesSemMudancaInd = 0, geracoesSemMudancaMedia = 0, maximoGeracoesSemMudanca = 10, tamPop = 50, it = 0, tamCromossomo = 0;
    double taxaSelecaoMelhor = 1, taxaCrossover = 1, taxaMutacao = 0.3, melhorPassado, mediaAntiga, limiarMudanca = 0.1;

    Individuo[] populacao;
    Individuo melhorInd;
    double[][] distancias;
    
    public AlgoritmoGenetico(double lat, double lon, List<Agencia> listaAgencias)
    {
        populacao = new Individuo[tamPop];
        distancias = new double[listaAgencias.size()+1][listaAgencias.size()+1];
        tamCromossomo = listaAgencias.size() + 2;
        
        for (int i = 0; i < distancias.length-1; i++) {
            distancias[0][i+1] = Distancia.distanciaKM(lat, lon, listaAgencias.get(i).getLat(), listaAgencias.get(i).getLon());
        }
        for (int i = 0; i < distancias.length-1; i++) {
            distancias[i+1][0] = Distancia.distanciaKM(listaAgencias.get(i).getLat(), listaAgencias.get(i).getLon(), lat, lon);
        }
        for (int i = 0; i < distancias.length-1; i++) {
            for (int j = 0; j < distancias.length-1; j++) {
                if(i != j)
                    distancias[i+1][j+1] = Distancia.distanciaKM(listaAgencias.get(i).getLat(), listaAgencias.get(i).getLon(), listaAgencias.get(j).getLat(), listaAgencias.get(j).getLon());
                else
                    distancias[i][j] = 0;
                System.out.print(distancias[i][j] + " ");
            }
            System.out.println("");
        }

        for(int i = 0; i < tamPop; i++)
        {
            populacao[i] = new Individuo(distancias);
            populacao[i].inicializarAleatorio(tamCromossomo);
        }
        
    }
    
    public void Roda()
    {
        Individuo[] auxNovaPopulacao, novaPopulacao, populacaoMutada;
        System.out.println("\nPopulacao Inicial");
        for(int i = 0; i < tamPop; i++)
        {
            System.out.println(populacao[i]);
        }
        double[] fitnessMaximo = new double[nIteracoes];
        double[] fitnessMedio = new double[nIteracoes];
        do
        {
            for(int i = 0; i < tamPop; i++)
            {
                populacao[i].calculaFuncaoObjetivo();
            }
            melhorPassado = EscolheMelhor(populacao).calculaFuncaoObjetivo();
            mediaAntiga = TiraMedia(populacao);
            fitnessMaximo[it] = melhorPassado;
            fitnessMedio[it] = mediaAntiga;
            auxNovaPopulacao = SelecionaPopulacao(populacao, taxaSelecaoMelhor);
            novaPopulacao = Crossover(auxNovaPopulacao, taxaCrossover);
            populacaoMutada = Mutacao(novaPopulacao, taxaMutacao);
        
            System.arraycopy(populacaoMutada, 0, populacao, 0, populacao.length);
            
            it++;
        }
        while(condicaoDeParada());

        fitnessMaximo[it-1] = EscolheMelhor(populacao).calculaFuncaoObjetivo();
        fitnessMedio[it-1] = TiraMedia(populacao);
//        System.out.println("\nFitness Medio:");
//        for (int i = 0; i < it; i++)
//        {
//            System.out.println(fitnessMedio[i]);
//        }
//        System.out.println("\nFitness Maximo:");
//        for (int i = 0; i < it; i++)
//        {
//            System.out.println(fitnessMaximo[i]);
//        }
        
        //*
        System.out.println("-------------Torneio---------------");
        for(int i = 0; i < tamPop / 2; i++)
        {
            System.out.println(auxNovaPopulacao[i]);
        }
        System.out.println("-------------Crossover-------------");
        for(int i = 0; i < tamPop; i++)
        {
            System.out.println(novaPopulacao[i]);
        }
        System.out.println("--------------Mutacao--------------");
        for(int i = 0; i < tamPop; i++)
        {
            System.out.println(populacaoMutada[i]);
        }
        melhorInd = EscolheMelhor(populacao);
        System.out.println("\nPopulacao Final");
        for(int i = 0; i < tamPop; i++)
        {
            System.out.println(populacao[i]);
        }
        
        System.out.println("Resultado pelo algoritmo genetico: " + melhorInd);
        //*/
    }
    
    private Individuo[] Crossover(Individuo[] populacao, double taxaCrossover) {
        Individuo[] novaPopulacao = new Individuo[populacao.length * 2];
        Individuo[] embaralhada = new Individuo[populacao.length];

        System.arraycopy(populacao, 0, embaralhada, 0, populacao.length);

        Collections.shuffle(Arrays.asList(embaralhada));

        for(int i = 0; i < populacao.length * 2; i++)
        {
            novaPopulacao[i] = new Individuo(distancias);
            novaPopulacao[i].inicializarAleatorio(tamCromossomo);
        }
        
        int tamanho = populacao[0].cromossomo.length;
        for(int i = 0; i < populacao.length; i++)
        {
        List<Integer> mapeamento1 = new ArrayList<Integer>();
        List<Integer> mapeamento2 = new ArrayList<Integer>();
            if(Math.random() < taxaCrossover)
            {
                int r = 0, s = 0;
                r = 1 + new Random().nextInt(tamanho-3);
                do
                {
                    s = 1 + new Random().nextInt(tamanho-2);
                }while(r >= s);
                for (int j = r; j <= s; j++)
                {
                    mapeamento1.add(populacao[i].cromossomo[j]);
                    mapeamento2.add(embaralhada[i].cromossomo[j]);
                }
                for (int j = 0; j < populacao[i].cromossomo.length; j++) {
                    int gene = populacao[i].cromossomo[j];
                    if(mapeamento1.contains((Object) gene))
                    {
                        gene = mapeamento2.get(mapeamento1.indexOf((Object) gene));
                    }
                    novaPopulacao[i*2].cromossomo[j] = gene;
                }
                List<Integer> repetidos = getRepetidos(novaPopulacao[i*2].cromossomo);
                
                while(!repetidos.isEmpty())
                {
                    for (Integer integer : repetidos) {
                        int geneNovo = novaPopulacao[i*2].cromossomo[integer];
                        if(mapeamento2.contains((Object) geneNovo))
                        {
                            geneNovo = mapeamento1.get(mapeamento2.indexOf((Object) geneNovo));
                        }
                        novaPopulacao[i*2].cromossomo[integer] = geneNovo;
                    }
                    repetidos = getRepetidos(novaPopulacao[i*2].cromossomo);
                }
                
                for (int j = 0; j < populacao[i].cromossomo.length; j++) {
                    int gene = populacao[i].cromossomo[j];
                    if(mapeamento1.contains((Object) gene))
                    {
                        gene = mapeamento2.get(mapeamento1.indexOf((Object) gene));
                    }
                    novaPopulacao[i*2+1].cromossomo[j] = gene;
                }
                List<Integer> repetidos2 = getRepetidos(novaPopulacao[i*2+1].cromossomo);
                
                while(!repetidos2.isEmpty())
                {
                    for (Integer integer : repetidos2) {
                        int geneNovo = novaPopulacao[i*2+1].cromossomo[integer];
                        if(mapeamento2.contains((Object) geneNovo))
                        {
                            geneNovo = mapeamento1.get(mapeamento2.indexOf((Object) geneNovo));
                        }
                        novaPopulacao[i*2+1].cromossomo[integer] = geneNovo;
                    }
                    repetidos2 = getRepetidos(novaPopulacao[i*2+1].cromossomo);
                }
            }
            else
            {
                novaPopulacao[i*2] = populacao[i];
                novaPopulacao[i*2+1] = embaralhada[i];
            }
        }
        for (int i = 0; i < novaPopulacao.length; i++) {
            novaPopulacao[i].calculaFuncaoObjetivo();            
        }
        return novaPopulacao;
    }
    
    private List<Integer> getRepetidos(int[] vetor)
    {
        List<Integer> repetidos = new ArrayList<Integer>();
        for (int j = 1; j < vetor.length-1; j++) {
            for (int k = j+1; k < vetor.length-1; k++) {
                if(vetor[j] == vetor[k]){
                    repetidos.add(k);
                }
            }
        }
        return repetidos;
    }
    
    private Individuo[] Mutacao(Individuo[] populacao, double taxaMutacao) {
        Individuo[] novaPopulacao = new Individuo[populacao.length];

        for(int i = 0; i < novaPopulacao.length; i++)
        {
            novaPopulacao[i] = new Individuo(distancias);
            novaPopulacao[i].inicializarAleatorio(tamCromossomo);
        }
        
        int tamanho = populacao[0].cromossomo.length;
        
        for(int i = 0; i < novaPopulacao.length; i++)
        {
                if(Math.random() < taxaMutacao)
                {
                    int r = 0, s = 0, aux;
                    r = 1 + new Random().nextInt(tamanho-2);
                    do
                    {
                        s = 1 + new Random().nextInt(tamanho-2);
                    }while(r == s);
                    aux = novaPopulacao[i].cromossomo[r];
                    novaPopulacao[i].cromossomo[r] = novaPopulacao[i].cromossomo[s];
                    novaPopulacao[i].cromossomo[s] = aux;
                }
                else
                {
                    novaPopulacao[i].cromossomo = populacao[i].cromossomo;
                }
        }
        return novaPopulacao;
    }
    
    private Individuo[] SelecionaPopulacao(Individuo[] populacao, double taxaSelecaoMelhor)
    {
        Individuo novaPopulacao[] = new Individuo[populacao.length / 2];
        for(int i = 0; i < populacao.length / 2; i++)
        {
            novaPopulacao[i] = new Individuo(distancias);
            novaPopulacao[i].inicializarAleatorio(tamCromossomo);
        }
        for(int i = 0; i < populacao.length / 2; i++)
        {
            int i1 = (int) (Math.random() * populacao.length);
            int i2 = (int) (Math.random() * populacao.length);
            if(populacao[i1].funcaoObjetivo >= populacao[i2].funcaoObjetivo)
            {
                if(Math.random() < taxaSelecaoMelhor)
                    novaPopulacao[i] = populacao[i1];
                else
                    novaPopulacao[i] = populacao[i2];
            }
            else
            {
                if(Math.random() < taxaSelecaoMelhor)
                    novaPopulacao[i] = populacao[i2];
                else
                    novaPopulacao[i] = populacao[i1];
            }
        }
        Individuo melhor = EscolheMelhor(populacao);
        int pior = 0;
        for(int i = 0; i < novaPopulacao.length; i++)
        {
            if(novaPopulacao[i].funcaoObjetivo > novaPopulacao[pior].funcaoObjetivo)
                pior = i;
        }
        novaPopulacao[pior] = melhor;
        return novaPopulacao;
    }
    
    private boolean condicaoDeParada()
    {
        double melhorAtual = EscolheMelhor(populacao).calculaFuncaoObjetivo(), media = TiraMedia(populacao);
        if(it >= nIteracoes)
        {
            System.out.println(it);
            return false;
        }
        if((Math.abs(melhorAtual - melhorPassado) < limiarMudanca))
        {
            geracoesSemMudancaInd++;
            if(geracoesSemMudancaInd > maximoGeracoesSemMudanca)
            {
                System.out.println("Mais de " + maximoGeracoesSemMudanca + " geracoes sem mudanca no melhor individuo. Parando programa na iteracao " + it + ".");
                return false;
            }
        }
        else
            geracoesSemMudancaInd = 0;
        if((Math.abs((media - mediaAntiga)) < limiarMudanca))
        {   
            geracoesSemMudancaMedia++;
            if(geracoesSemMudancaMedia > maximoGeracoesSemMudanca)
            {
                System.out.println("Mais de " + maximoGeracoesSemMudanca + " geracoes sem mudanca na media da populacao. Parando programa na iteracao " + it + ".");
                return false;
            }
        }
        else
            geracoesSemMudancaMedia = 0;
        return true;
    }
    
    private Individuo EscolheMelhor(Individuo[] populacao)
    {
        int melhor = 0;
        for(int i = 0; i < populacao.length; i++)
        {
            if(populacao[i].funcaoObjetivo < populacao[melhor].funcaoObjetivo)
                melhor = i;
        }
        return populacao[melhor];
    }
    
    
    private double TiraMedia(Individuo[] populacao)
    {
        double media = 0;
        for(int i = 0; i < populacao.length; i++)
        {
            media += populacao[i].calculaFuncaoObjetivo();
        }
        media /= populacao.length;
        return media;
    }
    
    public int[] getMelhorIndividuo()
    {
        return this.melhorInd.cromossomo;
    }

    public double getLimiarMudanca() {
        return limiarMudanca;
    }

    public void setLimiarMudanca(double limiarMudanca) {
        this.limiarMudanca = limiarMudanca;
    }

    public int getMaximoGeracoesSemMudanca() {
        return maximoGeracoesSemMudanca;
    }

    public void setMaximoGeracoesSemMudanca(int maximoGeracoesSemMudanca) {
        this.maximoGeracoesSemMudanca = maximoGeracoesSemMudanca;
    }
}
